class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        """这样会超时"""
        len_s, len_t, res = len(s), len(t), 0
        if len_t > len_s:
            return 0
        for i in range(2 ** len_s):
            mid_str = bin(i)[2:].rjust(len_s, "0")
            if mid_str.count("1") == len_t:
                mid_s = ""
                for j in range(len(mid_str)):
                    mid_s += s[j] * int(mid_str[j])
                if mid_s == t:
                    res += 1
        return res


class Solution2:
    """这个也会超时,比上一个好一点"""
    def numDistinct(self, s: str, t: str) -> int:
        mid_s = ""
        for i in range(len(s)):
            if s[i] in t:
                mid_s += s[i]
        self.len_s, len_t, res = len(mid_s), len(t), 0
        if len_t > self.len_s:
            return 0
        self.zhizhen_list = [i for i in range(len_t)]
        while self.zhizhen_list[0] <= self.len_s - len_t:
            # print(self.zhizhen_list)
            mid_str = ""
            for i in range(len_t):
                mid_str += mid_s[self.zhizhen_list[i]]
            if mid_str == t:
                res += 1
            try:
                self.jin_wei(-1)
            except:
                return res

    def jin_wei(self, i):
        if self.zhizhen_list[i] - i >= self.len_s:
            self.zhizhen_list[i] = self.jin_wei(i - 1) + 1
        else:
            self.zhizhen_list[i] += 1
        return self.zhizhen_list[i]


class Solution3:
    def numDistinct(self, s: str, t: str) -> int:
        mid_s, set_t = "", set(t)
        for i in range(len(s)):
            if s[i] in set_t:
                mid_s += s[i]
        s = mid_s
        len_s, len_t = len(s), len(t)
        if len_t > len_s:
            return 0
        dp = [[0 for j in range(len_s+1)] for i in range(len_t+1)]
        for j in range(len_s+1):
            dp[0][j] = 1
        for i in range(1, len_t+1):
            for j in range(1, len_s + 1):
                if s[j-1] == t[i-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
                else:
                    dp[i][j] = dp[i][j-1]
        return dp[-1][-1]


a = Solution3()
print(a.numDistinct("rabbbit", "rabbit"))
